import java.util.*;
class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

public class Test {
    /*
    题目 1：反转单链表
     */
    // 使用栈解决
    public ListNode ReverseList1(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        Stack<ListNode> stack = new Stack<>();
        while(head != null){
            stack.push(head);
            head = head.next;
        }
        head = stack.pop();
        ListNode cur = head;
        while(!stack.isEmpty()){
            cur.next = stack.pop();
            cur = cur.next;
        }
        cur.next = null;
        return head;
    }

    //方法二：双链表求解
    //把原链表的结点一个个摘下，每次摘掉的链表都让他成为新链表的头节点
    //有点类似于 头插法
    public static ListNode ReverseList2(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }

        ListNode cur = head.next;

        ListNode node = null;
        ListNode head1 = head;
        head1.next = null;


        while(cur != null){
            node = cur;
            node.next = head1;
            head1 = node;
            cur = cur.next;
        }

        return head1;
    }
    //上述写法中，node.next 相当于 cur.next ，修改 cur 的指向前，没有记录下 next 的地址
    //这里让我重新认识到，记录下 cur.next 地址的用处！
    public static ListNode ReverseList(ListNode head) {
        ListNode newHead = null;
        //每个结点摘掉，并重新排列时，并不需要留下旧的头部！
        while(head != null){
            //临时的结点记录 head.next 的地址
            ListNode temp = head.next;
            head.next = newHead;
            newHead = head;

            head = temp;
        }
        return newHead;
    }



    public static void main1(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        ListNode node = ReverseList(node1);
    }

    /*
    题目 2：合并两个有序链表
     */
    //最基本的想法是遍历两个链表吧
    //可以利用 哑节点 的方式来对昨天的写法进行简化！
    //使用 一个 辅助的头节点
    //这样一来，甚至都不需要单独去判断 两个链表是否为空的情况
    public ListNode Merge1(ListNode list1,ListNode list2) {
        ListNode newHead = new ListNode(0);//值是多少不重要
        ListNode cur = newHead;
        ListNode cur1 = list1;
        ListNode cur2 = list2;
        while(cur1 != null && cur2 != null){
            if(cur1.val < cur2.val){
                cur.next = cur1;
                cur = cur1;
                cur1 = cur1.next;

            }else{
                cur.next = cur2;
                cur = cur2;
                cur2 = cur2.next;
            }
        }

        if(cur1 != null){
            cur.next = cur1;
        }

        if(cur2 != null){
            cur.next = cur2;
        }

        return newHead.next;
    }

    //方法二： 用递归的方式
    //使用递归的方式，更简洁阿！
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1 == null){
            return list2;
        }else if(list2 == null){
            return list1;
        }else if(list1.val < list2.val){
            list1.next = Merge(list1.next, list2);
            return list1;
        }else{
            list2.next = Merge(list1, list2.next);
            return list2;
        }
    }

    /*
    题目 3：链表中最后 k 个结点
     */
    //方法一：快慢指针
    public ListNode FindKthToTail (ListNode pHead, int k) {
        ListNode fast = pHead;
        ListNode slow = pHead;

        for(int i = 0; i < k; i++){
            if(fast != null){
                fast = fast.next;
            }else{
                return null;
            }
        }

        while(fast != null){
            fast = fast.next;
            slow = slow.next;
        }

        return slow;
    }

    /*
    题目 4：删除有序链表中重复的元素Ⅰ
     */
    //遍历删除
    public ListNode deleteDuplicates (ListNode head) {
        ListNode cur = head;
        while(cur != null && cur.next != null){
            if(cur.val == cur.next.val){
                cur.next = cur.next.next;
            }else{
                cur = cur.next;
            }
        }
        return head;
    }

    /*
    题目 5 ：链表的奇偶重排
     */
    public ListNode oddEvenList (ListNode head) {
        if(head == null){
            return head;
        }
        ListNode oddHead = head;
        ListNode evenHead = head.next;
        ListNode odd = oddHead;
        ListNode even = evenHead;

        //只有链表中有三个及以上的结点，才进入循环
        while(even != null && even.next != null){
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }

        odd.next = evenHead;

        return head;
    }




}
